package org.pjl.algorithm;

public class AlgorithmOfSorting {

	/**
	 * 直接插入排序(稳定) 直接插入排序的过程为：
	 * 在插入第i个记录时，R1,R2,..Ri-1已经排好序，将第i个记录的排序码Ki依次和R1,R2,..,Ri
	 * -1的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。
	 * 
	 * @param array
	 * @return
	 */
	public static int[] insertionSort(int[] array) {
		if (array == null || (array != null && array.length < 2)) {
			return array;
		}

		for (int i = 1; i < array.length; i++) {
			int base = array[i];
			int j = i - 1;
			while (j >= 0 && array[j] > base) {
				array[j + 1] = array[j];
				j--;
			}
			array[j + 1] = base;
		}

		return array;
	}

	/**
	 * 希尔排序(不稳定)： 希尔(Shell)排序的基本思想是： 先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。
	 * 所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，
	 * 取得第二个增量d2<d1重复上述的分组和排序，直至所取的增量di=1，
	 * 即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
	 * 一般取d1=n/2，di+1=di/2。如果结果为偶数，则加1，保证di为奇数。
	 * 希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平均时间复杂度为O(n^1.3).
	 * 
	 * @param array
	 * @return
	 */
	public static int[] shellSort(int[] array) {
		if (array == null || (array != null && array.length < 2)) {
			return array;
		}

		int i, k, t;
		k = (array.length / 2) % 2 == 0 ? array.length / 2 + 1 : array.length / 2;// 保证增量为奇数
		while (k > 0) {
			for (int j = k; j < array.length; j++) {
				t = array[j];
				i = j - k;
				while (i >= 0 && array[i] > t) {
					array[i + k] = array[i];
					i = i - k;
				}
				array[i + k] = t;
			}
			if (k == 1) {
				break;
			}
			k = (k / 2) % 2 == 0 ? k / 2 + 1 : k / 2;// 保证增量为奇数
		}

		return array;
	}

	/**
	 * 直接选择排序(不稳定) 直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，
	 * 然后在其余的记录内选出排序码最小的记录，与第2个记录交换 ......依次类推，直到所有记录排完为止。
	 * 无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较， 因此，
	 * 总的比较次数为n*(n-1)/2=O(n^2)。当初始文件为正序时 ，移动次数为0；文件初态为反序时，
	 * 每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O (n^2)。 直接选择排序是不稳定的。
	 * 
	 * @param array
	 * @return
	 */
	public static int[] selectSort(int[] array) {
		if (array == null || (array != null && array.length < 2)) {
			return array;
		}
		int tmp = 0;
		for (int i = 0; i < array.length; i++) {

			// 寻找最小值
			int minIndex = i;
			for (int j = i + 1; j < array.length; j++) {
				if (array[j] < array[minIndex]) {
					minIndex = j;
				}
			}

			if (minIndex != i) {
				// 找到最小值则进行交换
				tmp = array[i];
				array[i] = array[minIndex];
				array[minIndex] = tmp;
			}

		}

		return array;
	}

	/**
	 * 
	 * 冒泡排序(稳定的) 冒泡排序将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为ki的气泡。
	 * 根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R ； 凡扫描到违反本原则的轻气泡，就使其向上"漂浮"。 如此反复进行，
	 * 直到最后任何两个气泡都是轻者在上，重者在下为止。
	 * 
	 * @param array
	 * @return
	 */
	public static int[] bubbleSort1(int[] array) {
		if (array != null && array.length > 1) {
			int tmp = 0, countOfMove = 0;
			for (int i = 1; i < array.length; i++) {// 只需要n-1次就可以
				boolean sorted = true; // 已经是排好序的

				for (int j = array.length - 1; j > 0; j--) {// 将轻的气泡浮到上面
					if (array[j - 1] > array[j]) {
						tmp = array[j - 1];
						array[j - 1] = array[j];
						array[j] = tmp;
						sorted = false; // 经过交换了
						countOfMove += 3;
					}
				}
				if (sorted) { // 如果这一轮没有经过交换，则已经是排好序的，下轮就不走了
					break;
				}
			}
			System.out.println("移动次数：" + countOfMove);
		}

		return array;
	}

	public static int[] bubbleSort2(int array[]) {
		// 优化的冒泡排序
		if (array != null && array.length > 1) {
			int countOfMove = 0, t, flag;
			for (int i = 0; i < array.length - 1; i++) {
				flag = 0;

				for (int j = 0; j < array.length - 1; j++) { // 将重的气泡沉到地下
					if (array[j + 1] < array[j]) {
						t = array[j];
						array[j] = array[j + 1];
						array[j + 1] = t;
						flag = 1;
						countOfMove += 3;
					}
				}
				if (flag == 0)
					break;
			}
			System.out.println("移动次数：" + countOfMove);
		}
		return array;
	}

	/**
	 * 快速排序：(不稳定的) 快速排序采用了一种分治的策略，通常称其为分治法， 其基本思想是： 将原问题分解为若干个规模更小但结构与原问题相似的子问题。
	 * 递归地解这些子问题 ，然后将这些子问题的解组合为原问题的解。 快速排序的具体过程如下：
	 * 第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组
	 * ，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码， 并把该记录排在这两组中间。
	 * 第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。
	 * 
	 * @param array
	 * @return
	 */
	public static int[] quickSort(int array[]) {
		if (array != null && array.length > 1) {
			quickSortSub2(array, 0, array.length - 1);
		}

		return array;
	}

	private static void quickSortSub(int[] array, int left, int right) {
		if (left < right) {
			int temp;
			int l = left, r = right;
			int base = array[left];

			while (l < r) {

				while (l >= left && array[l] < base) {
					// 左边的小于基准值则向右移
					l++;
				}

				while (r <= right && array[r] > base) {
					// 右边的大于基准值则向左移
					r--;
				}

				if (r > l) {
					temp = array[l];
					array[l] = array[r];
					array[r] = temp;
				}
			}
			quickSortSub(array, left, l - 1);
			quickSortSub(array, l + 1, right);
		}
	}

	/** 快速排序方法 */
	private static void quickSortSub2(int[] a, int left, int right) {
		int lo = left;
		int hi = right;

		if (lo >= hi)
			return;

		// 确定指针方向的逻辑变量
		boolean transfer = true;

		while (lo != hi) {
			if (a[lo] > a[hi]) {
				// 交换数字
				int temp = a[lo];
				a[lo] = a[hi];
				a[hi] = temp;
				// 决定下标移动，还是上标移动
				transfer = !transfer;
			}

			// 将指针向前或者向后移动
			if (transfer)
				hi--;
			else
				lo++;

			// 显示每一次指针移动的数组数字的变化

			for (int i = 0; i < a.length; ++i) {
				System.out.print(a[i] + ",");
			}
			System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
			System.out.println("");

		}

		// 将数组分开两半，确定每个数字的正确位置
		lo--;
		hi++;
		quickSortSub2(a, left, lo);
		quickSortSub2(a, hi, right);
	}

	public static int[] mergeSort(int[] array) {
		if (array != null && array.length > 1) {
			int[] temp = new int[array.length];
			mergeSortSub(array, 0, array.length - 1, temp);
		}
		return array;
	}

	private static void mergeSortSub(int[] array, int from, int to, int[] temp) {
		if (from < to) {
			int mid = (from + to) / 2;
			mergeSortSub(array, from, mid, temp);
			mergeSortSub(array, mid + 1, to, temp);
			merge(array, from, to, mid, temp);
		}
	}

	private static void merge(int[] array, int from, int to, int middle, int[] temporary) {
		int k = 0, leftIndex = 0, rightIndex = to - from;
		System.arraycopy(array, from, temporary, 0, middle - from + 1);
		for (int i = 0; i < to - middle; i++) {
			temporary[to - from - i] = array[middle + i + 1];
		}
		while (k < to - from + 1) {
			if (temporary[leftIndex] < (temporary[rightIndex])) {
				array[k + from] = temporary[leftIndex++];
			} else {
				array[k + from] = temporary[rightIndex--];
			}
			k++;
		}
	}

	// private void merge(long[] workSpace, int lowPtr, int highPtr, int
	// upperBound) {
	// int j = 0;
	// int lowerBound = lowPtr;
	// int mid = highPtr - 1;
	// int n = upperBound - lowerBound + 1;
	// while (lowPtr <= mid && highPtr <= upperBound) {
	// if (theArray[lowPtr] < theArray[highPtr]) {
	// workSpace[j++] = theArray[lowPtr++];
	// } else {
	// workSpace[j++] = theArray[highPtr++];
	// }
	// }
	// while (lowPtr <= mid) {
	// workSpace[j++] = theArray[lowPtr++];
	// }
	// while (highPtr <= upperBound) {
	// workSpace[j++] = theArray[highPtr++];
	// }
	// for (j = 0; j < n; j++) {
	// theArray[lowerBound + j] = workSpace[j];
	// }
	// }
}
